package com.eloancn.leecode.sort;

import org.junit.Test;

import java.util.Arrays;


/**
 * 希尔排序
 * @author lihepeng
 *	 希尔排序主要意思在于对内容进行分组
 * 然后逐渐的缩小分组 从而达到最后只剩下一组即所有的内容都是排序的
 * 	临江仙
 * 滚滚长江东逝水，浪花淘尽英雄。是非成败转头空。青山依旧在，几度夕阳红。白发渔樵江渚上，惯看秋月春风。一壶浊酒喜相逢。古今多少事，都付笑谈中。
 */
public class ShellSort {
	public static void main(String[] args) {
		int arr [] = {1,4,2,7,9,8,3,6};
		shellSort(arr);
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}
	// 使用交换算法
	public static void  shellSort(int[] arr ) {
		for(int gap = arr.length/2;gap>0;gap/=2) {
			//针对gap里面的元素进行排序
			for(int i=gap ;i<arr.length;i++) {
				int j = i;
				while(j-gap>=0 && arr[j]<arr[j-gap]) {
					swap(arr,j,j-gap);
					j-=gap;
				}
			}
		}
	}
	@Test
	public void runTest() {
		int arr [] = {1,4,2,7,9,8,3,6};
		shellSort(arr);
		String string = Arrays.toString(arr);
		System.out.println(string);
	}
	
	public void shellSort1(int []arr) {
		for (int gap = arr.length/2; gap >0 ; gap/=2) {
			// 针对分好组之后的内容进行排序
			for(int i =0;i<gap;i++) {
				int j = i;
				while(gap+j<arr.length && arr[j]>arr[gap+j]) {
					swap(arr, j, j+gap);
					j+=gap;
				}
			}
		}
	}

	private static void swap(int[] arr, int j, int i) {
		int temp = arr[j];
		arr[j] = arr[i];
		arr[i] = temp;
	}
	/**
	 * 希尔排序使用
	 */
	public void shellSort3(int[] arr) {
		for(int gap = arr.length/2;gap>0;gap /=2) {
			for(int i = gap;i<arr.length;i++) {
				int j =i;
				while(j-gap>0 && arr[j]>arr[j-gap]) {
					swap(arr, j, j-gap);
					j-=gap;
				}
			}
		}
	}
	@Test
	public void runTest03() {
		int arr [] = {1,4,2,7,9,8,3,6};
		shellSort3(arr);
		System.out.println(Arrays.toString(arr));
	}
	
}
